package com.maishi.programmer.jainzhioffer;

import com.fasterxml.jackson.databind.util.LinkedNode;

/**
 * Created by brossdong on 2018/3/26.
 * 输入一个链表，输出该链表中倒数第k个结点。
 */
public class TestProblem22 {


    /**
     * 构造单链表
     */
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    /**
     * 为了符合大多数人的习惯，本题从1開始计数，即链表的尾结点是倒数第1个结点。
     * 比如一个链表有6个结点。从头结点開始它们的值依次是1。2。3，4，5。6.
     * 这个链表的倒数第3个结点是值为4的结点
     * @param head
     * @param k
     * @return
     */
    public ListNode FindKthToTail(ListNode head,int k) {
        //表头不为空
        if (head == null || k <= 0) return null;

        //
        ListNode node1 = head;
        ListNode node2 = null;
        for (int i = 0;i < k-1;i++) {
            if (node1.next != null) {
                node1 = node1.next;
            } else {
                return null;
            }
        }
        node2 = head;
        while (node1.next != null) {
            node1 = node1.next;
            node2 = node2.next;
        }
        return node2;
    }


}
